package struct.primary.array;

/**
 * @author MAX
 * @version 1.0
 * @description 初级数据结构-动态数组
 * @date 2022/1/11 15:39
 */
public class Array<E> {

    private E[] data;
    //记录元素存储个数
    private int size;

    public Array() {
        this(10);
    }

    public Array(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be greater than zero");
        data = (E[])new Object[capacity];
        size = 0;
    }

    public Array(E[] arr) {
        data = (E[])new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }

        size = arr.length;
    }

    /**
     * 获取元素个数
     *
     * @return 元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 获取数组容量
     *
     * @return 数据容量
     */
    public int capacity() {
        return data.length;
    }

    /**
     * 数组是否为空
     *
     * @return 判断结果
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 末尾追加
     *
     * @param e 追加元素
     */
    public void addLast(E e) {
        if (isFull()) resize(data.length * 2);
        data[size++] = e;
    }

    /**
     * 头部追加
     *
     * @param e 追加元素
     */
    public void addFirst(E e) {
        add(0, e);
    }

    /**
     * 指定位置插入新元素
     *
     * @param index 插入下标
     * @param e     插入元素
     */
    public void add(int index, E e) {
        if (index < 0 || index > size) throw new IllegalArgumentException("Index-base0 out of boundary");
        if (isFull()) resize(data.length * 2);

        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }

        data[index] = e;
        size++;
    }

    private void resize(int capacity) {
        E[] newData = (E[])new Object[capacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    /**
     * 修改指定下标的元素
     *
     * @param index 元素下标
     * @param e     替换元素
     */
    public void set(int index, E e) {
        if (index < 0 || index > size) throw new IllegalArgumentException("Index-base0 out of boundary");
        data[index] = e;
    }

    /**
     * 根据下标获取元素
     *
     * @param index 下标
     * @return 下标对应元素
     */
    public E get(int index) {
        if (isEmpty()) throw new IllegalArgumentException("Array Empty");
        if (index < 0 || index > size) throw new IllegalArgumentException("Index-base0 out of boundary");

        return data[index];
    }

    /**
     * 是否包含指定元素
     * @param e 检查元素
     * @return 检查结果
     */
    public boolean contains(E e) {
        if (isEmpty()) throw new IllegalArgumentException("Array Empty");
        for (int i = 0; i < size; i++) {
            if (data[i] == e) return true;
        }

        return false;
    }

    /**
     * 返回首个匹配元素下标
     * @param e 匹配元素
     * @return 匹配元素下标
     */
    public int find(E e) {
        if (isEmpty()) throw new IllegalArgumentException("Array Empty");
        for (int i = 0; i < size; i++) {
            if (data[i] == e) return i;
        }

        return -1;
    }

    /**
     * 删除指定索引下的元素
     * @param index 指定索引
     * @return 被删除元素
     */
    public E remove(int index) {
        if (isEmpty()) throw new IllegalArgumentException("Array Empty");
        if (index < 0 || index > size) throw new IllegalArgumentException("Index-base0 out of boundary");

        E ret = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }

        size--;
        data[size] = null;
        if(size <= data.length / 3) resize(data.length / 2);
        return ret;
    }

    /**
     * 删除首部元素
     * @return e
     */
    public E removeFirst() {
        return remove(0);
    }

    /**
     * 删除尾部元素
     * @return e
     */
    public E removeLast() {
        return remove(size - 1);
    }

    /**
     * 删除首个匹配元素
     * @param e 删除元素
     * @return 删除元素
     */
    public void removeByElement(E e) {
        if (isEmpty()) throw new IllegalArgumentException("Array Empty");
        int removeIndex = find(e);
        if(removeIndex != -1) remove(removeIndex);

    }


    /**
     * 是否存在剩余空间
     * @return 判断结果
     */
    private boolean isFull() {
        return size == data.length;
    }

    public void swap(int i, int j) {
        if(i < 0 || i >= size || j < 0 || j >= size) throw new IllegalArgumentException("index is exception");
        E e = data[i];
        data[i] = data[j];
        data[j] = e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("[");
        for (int i = 0; i < size; i++) {
            res.append(data[i]);
            if (i + 1 != size) res.append(",");
        }
        res.append("]");

        return res.toString();
    }
}
